"""
给定一个数组，每次取出最大值，并将其根再塞回去
重复k次操作，问最后剩下的数的总和是多少
"""
import heapq
import math
from typing import List

class T(object):
    """
    放入堆中的元素类型，需要重载<，返回true的排在更上面
    """
    def __init__(self, v: int) -> None:
        self.value = v
    def __lt__(self, other: 'T') -> bool: 
        return self.value > other.value

class Solution:
    def pickGifts(self, gifts: List[int], k: int) -> int:
        H = [] # 用数组来保存堆
        for i in gifts: # 建堆
            heapq.heappush(H, T(i)) # push，注意push的类型
        for i in range(k):
            h = heapq.heappop(H) # 取top，注意取出的类型
            heapq.heappush(H, T(int(math.sqrt(h.value))))
        ans = 0
        while len(H) != 0:
            h = heapq.heappop(H)
            ans += h.value
        return ans